package com.algorithm.ch1.lzr.string;

/**
 * 最长公共前缀
 *
 * @author lzr
 * @date 2018/8/16
 */
public class LongestCommonPrefix {

    public static void main(String[] args) {
        String[] strArray1 = {"aa", "a"};
        String s1 = longestCommonPrefix1(strArray1);
        System.out.println(s1);

        String[] strArray2 = {"fly", "flight", "float"};
        String s2 = longestCommonPrefix2(strArray2);
        System.out.println(s2);
    }

    /**
     * 获取字符数组的最长公共前缀
     *
     * T(N) = n^2
     *
     * @param strArray
     * @return
     */
    public static String longestCommonPrefix1(String[] strArray) {
        if (strArray.length == 0 || strArray[0].length() == 0) {
            return "";
        }
        if (strArray.length == 1) {
            return strArray[0];
        }
        int k = 0;
        char c = strArray[0].charAt(k);
        for (int i = 1; i < strArray.length; i++) {
            String str = strArray[i];
            if (k >= str.length()) {
                return str.substring(0, k);
            }
            if (c != str.charAt(k)) {
                return str.substring(0, k);
            }
            if (i == strArray.length - 1) {
                i = 0;
                ++k;
                if (k >= strArray[0].length()) {
                    return str.substring(0, k);
                } else {
                    c = strArray[0].charAt(k);
                }
            }
        }
        return strArray[0].substring(0, k);
    }


    /**
     * 另一种方法
     *
     * @param strArray
     * @return
     */
    private static String longestCommonPrefix2(String[] strArray) {
        int count = strArray.length;
        String prefix = "";
        if (count != 0) {
            prefix = strArray[0];
        }
        for (int i = 0; i < count; i++) {
            while (!strArray[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }
}
